<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>程序设计——问题求解 | 软工个人项目——拼图游戏</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="一、需求分析 以游戏问题作输入，能够求解简单的拼图游戏问题 对于彩色、黑白两种类型的游戏，均能有效求解  二、思路介绍在查阅相关资料后，知道拼图游戏问题是一个NP问题。因此，不存在多项式时间复杂度的问题求解算法。在对问题进行进一步分析，并参考网络、Github等资料，最终确定了通过深度优先搜索算法作为问题求解算法。 对于k种颜色，n*m规模的问题，显然问题的解空间为n*m,每个元素取值为[0,k-">
<meta property="og:type" content="article">
<meta property="og:title" content="程序设计——问题求解">
<meta property="og:url" content="http://bit-wxz.gitee.io/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/index.html">
<meta property="og:site_name" content="软工个人项目——拼图游戏">
<meta property="og:description" content="一、需求分析 以游戏问题作输入，能够求解简单的拼图游戏问题 对于彩色、黑白两种类型的游戏，均能有效求解  二、思路介绍在查阅相关资料后，知道拼图游戏问题是一个NP问题。因此，不存在多项式时间复杂度的问题求解算法。在对问题进行进一步分析，并参考网络、Github等资料，最终确定了通过深度优先搜索算法作为问题求解算法。 对于k种颜色，n*m规模的问题，显然问题的解空间为n*m,每个元素取值为[0,k-">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-02-03T06:25:54.000Z">
<meta property="article:modified_time" content="2021-02-04T12:53:09.139Z">
<meta property="article:author" content="王欣哲 1120182955">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/hexo/atom.xml" title="软工个人项目——拼图游戏" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/hexo/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/hexo/css/style.css">

  
    
<link rel="stylesheet" href="/hexo/fancybox/jquery.fancybox.min.css">

  
<meta name="generator" content="Hexo 5.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/hexo/" id="logo">软工个人项目——拼图游戏</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/hexo/" id="subtitle">王欣哲 1120182955</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/hexo/">Home</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/hexo/atom.xml" title="RSS 订阅"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="搜索"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="搜索"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://BIT-WXZ.gitee.io/hexo"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-程序设计——问题求解" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/" class="article-date">
  <time class="dt-published" datetime="2021-02-03T06:25:54.000Z" itemprop="datePublished">2021-02-03</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      程序设计——问题求解
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h2 id="一、需求分析"><a href="#一、需求分析" class="headerlink" title="一、需求分析"></a>一、需求分析</h2><ol>
<li>以游戏问题作输入，能够求解简单的拼图游戏问题</li>
<li>对于彩色、黑白两种类型的游戏，均能有效求解</li>
</ol>
<h2 id="二、思路介绍"><a href="#二、思路介绍" class="headerlink" title="二、思路介绍"></a>二、思路介绍</h2><p>在查阅相关资料后，知道拼图游戏问题是一个NP问题。因此，不存在多项式时间复杂度的问题求解算法。在对问题进行进一步分析，并参考网络、Github等资料，最终确定了通过深度优先搜索算法作为问题求解算法。</p>
<p>对于k种颜色，n*m规模的问题，显然问题的解空间为n*m,每个元素取值为[0,k-1]的所有矩阵的集合。使用DFS算法，对每个格点的取值进行穷举，即可求解出本问题。</p>
<p>时间复杂度:O(k^(m*n))</p>
<p>由于时间复杂度过高，因此本求解算法仅对小规模问题能进行有效的求解，而求解大规模问题所耗时间过长。通过在算法中添加有效的剪枝判定，可以在很大程度上降低算法的时间复杂度，这也是进一步改进求解算法的方向之一。</p>
<img src = "1.png" width = "700" alt="图3 类图" align=center />

<h2 id="三、代码实现"><a href="#三、代码实现" class="headerlink" title="三、代码实现"></a>三、代码实现</h2><p>下面的代码展示求解算法的c++代码实现。这个方法是Nonograms的一个私有方法，它由Nonograms的另外公有方法进行调用。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">Nonograms::dfs</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> _x = x + (y + <span class="number">1</span>) / pic.width;</span><br><span class="line">	<span class="keyword">int</span> _y = (y + <span class="number">1</span>) % pic.width;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span> (_x &gt;= pic.height) &#123;</span><br><span class="line">		<span class="keyword">return</span> check();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; pic.cNum; i++) &#123;</span><br><span class="line">		pic.mp[x][y] = i;</span><br><span class="line">		<span class="keyword">if</span> (dfs(_x, _y)) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="http://bit-wxz.gitee.io/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/" data-id="ckkva2tf80002nsms9f4g447f" data-title="程序设计——问题求解" class="article-share-link">分享</a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94%E5%91%BD%E4%BB%A4%E5%8F%B0/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">前一篇</strong>
      <div class="article-nav-title">
        
          运行展示——命令台
        
      </div>
    </a>
  
  
    <a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">后一篇</strong>
      <div class="article-nav-title">程序设计——拼图文件生成</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">归档</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2021/02/">二月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2021/01/">一月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2020/12/">十二月 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94GUI/">运行展示——GUI</a>
          </li>
        
          <li>
            <a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94%E5%91%BD%E4%BB%A4%E5%8F%B0/">运行展示——命令台</a>
          </li>
        
          <li>
            <a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a>
          </li>
        
          <li>
            <a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90/">程序设计——拼图文件生成</a>
          </li>
        
          <li>
            <a href="/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/">拼图游戏——综述</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2021 王欣哲 1120182955<br>
	  
	  
	   
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/hexo/" class="mobile-nav-link">Home</a>
  
</nav>
    


<script src="/hexo/js/jquery-3.4.1.min.js"></script>



  
<script src="/hexo/fancybox/jquery.fancybox.min.js"></script>




<script src="/hexo/js/script.js"></script>





  </div>
</body>
</html>